package 算法.leetcode.labuladong.数组和链表;

import java.util.PriorityQueue;

/**
 * @author lchenglong
 * @date 2022/6/18
 */
public class 环形数组中的最大和 {
    static class Solution {

        public static void main(String[] args) {
            Solution solution = new Solution();
            int[] nums = new int[]{9,-4,-7,9};
            int ans = solution.maxSubarraySumCircular(nums);
            System.out.println(ans);
        }
        // 尝试失败的
        public int maxSubarraySumCircular(int[] nums) {
            int n = nums.length;
            // 模拟环状的 nums 数组
            int[] preSum = new int[2 * n + 1];
            preSum[0] = 0;
            // 计算环状 nums 的前缀和
            for (int i = 1; i < preSum.length; i++) {
                preSum[i] = preSum[i - 1] + nums[(i - 1) % n];
            }
            // 记录答案
            int maxSum = Integer.MIN_VALUE;
            // 维护一个滑动窗口，以便根据窗口中的最小值计算最大子数组和
            PriorityQueue<Integer> window = new PriorityQueue<>();
            window.add(0);
            for (int i = 1; i < preSum.length; i++) {
                maxSum = Math.max(maxSum, preSum[i] - window.peek());
                // 维护窗口的大小为 nums 数组的大小
                if (window.size() == n) {
                    window.poll();
                }
                window.add(preSum[i]);
            }

            return maxSum;
        }
    }


}
